package com.wuyou.mid;

/**
 * 852. 山脉数组的峰顶索引
 */
public class PeakIndexInMountainArray {


    public static void main(String[] args) {
//        int[] arr = {0, 1, 0};
        int[] arr = {0, 2, 1, 0};
//        int[] arr = {24,69,100,99,79,78,67,36,26,19};
//        int[] arr = {3,5,3,2,0};

        System.out.println(sol_2(arr));
    }



    public static int sol_2(int[] arr) {
        // 初始化变量
        int l = 0, r = arr.length - 1, mid = arr.length / 2, targetIndex = 0;

        // 循环条件
        while (l <= r) {
            // mid - 1 <= mid <= mid + 1    mid 就是山峰 即最大值
            if(arr[mid] >= arr[mid - 1] && arr[mid] >= arr[mid + 1]){
                targetIndex = mid;
                break;
            }
            // mid <= mid + 1 左半边升序 山峰在右边 确定左边界为mid
            if(arr[mid] <= arr[mid + 1]){
                l = mid;
                mid = ((r - l) / 2) + l;
            }else {
                // 否则山峰即在左边 确定又边界为mid
                r = mid;
                mid = ((r - l) / 2) + l;
            }
        }
        return targetIndex;
    }
    public static int sol_1(int[] arr) {
        int l = 0, r = arr.length - 1, mid = 0, targetIndex = 0;

        while (l <= r) {
            mid = ((r - l) / 2) + l;
            if (arr[mid - 1] <= arr[mid] && arr[mid] >= arr[mid + 1]) {
                targetIndex = mid;
                break;
            }
            // 在此处陷入了简单二分的牛角尖 mid
            if (arr[mid] < arr[mid + 1]) {
                l = mid;
            } else {
                r = mid;
            }
        }
        return targetIndex;
    }
}
